#include <iostream>
using namespace std;

template<typename T>
T Graph<T>::MaxFlow(int src,int dest,T INF)
{
	int i,j;
	T k,flow = 0;
	Edge<T> *x;
	vector<Edge<T>*> cur,path(n);
	vector<int> d(n),q(n);
	for(;;)
	{
		//BFS
		int start,end;
		start = end = 0;
		q[end++] = src;
		for(i=0;i<d.size();i++)
			d[i] = -1;
		d[src] = 0;
		while(start < end)
		{
			i = q[start++];
			for(x=edge[i];x;x=x->next)
				if(x->flow < x->capacity && d[j=x->vertex] < 0)
				{
					d[j] = d[i]+1;
					q[end++] = j;
					if(j == dest) goto bfsend;//BFS complete
				}
		}
bfsend:
		if(d[dest] < 0) break;
		cur = edge;
		//DFS
		path.resize(0);
		for(;;)
		{
			i = path.size()==0 ? src : path[path.size()-1]->vertex;
			if(i == dest)//augment
			{
				int minj = 0;
				for(j=0,k=INF;j<path.size();j++)
					if(path[j]->capacity - path[j]->flow < k)
					{
						k = path[j]->capacity - path[j]->flow;
						minj = j;
					}
				flow += k;
				for(j=0;j<path.size();j++)
				{
					path[j]->flow += k;
					path[j]->back->flow -= k;
				}
				path.resize(minj);
				continue;
			}
			for(x=cur[i];x;x=x->next)
				if(x->flow < x->capacity && d[x->vertex] == d[i]+1)
					break;
			if(x)
			{
				path.push_back(x);
				cur[i] = cur[i]->next;
			}
			else
			{
				d[i] = -1;
				if(path.size() == 0) break;
				path.pop_back();
				cur[i] = edge[i];
			}
		}
	}
	return flow;
}